package leetcode;
import java.util.*;
import java.util.LinkedList;
import java.util.Queue;
class MedianFinder {
    List<Integer> list=null;
    /** initialize your data structure here. */
    public MedianFinder() {
        list=new ArrayList<>();
    }

    public void addNum(int num) {
        list.add(num);
    }
    public double findMedian() {
        Collections.sort(list);
        if (list.size()%2==1){
            return (double)list.get(list.size()/2);
        }
        return (double)(list.get(list.size()/2)+list.get(list.size()/2-1))/2.0;
    }
}
class KthLargest {
    PriorityQueue<Integer> pq;
    int k;

    public KthLargest(int k, int[] nums) {
        this.k = k;
        pq = new PriorityQueue<Integer>();
        for (int x : nums) {
            add(x);
        }
    }

    public int add(int val) {
        pq.offer(val);
        if (pq.size() > k) {
            pq.poll();
        }
        return pq.peek();
    }

}
public class LeetCodeMain119 {
    public int minCostClimbingStairs(int[] cost) {

        int[] dp=new int[cost.length];
        dp[0]=cost[0];
        dp[1]=cost[1];
        for (int i = 2; i < cost.length; i++) {
            dp[i]=Math.min(dp[i-1],dp[i-2])+cost[i];
        }
        return Math.min(dp[dp.length-1],dp[dp.length-2]);
    }
    public int peakIndexInMountainArray(int[] arr) {
        int[] nums=new int[arr.length];
        System.arraycopy(arr,0,nums,0,arr.length);
        Arrays.sort(nums);
        for (int i = 1; i < arr.length-1; i++) {
            if (nums[nums.length-1]==arr[i]){
                return i;
            }
        }
        return -1;
    }
    public boolean canPartitionKSubsets(int[] nums, int k) {
        int sum=0;
        for (int n:nums) {
            sum+=n;
        }
        if (sum%k!=0){
            return false;
        }
        int length=nums.length;
        boolean[] flag=new boolean[length];
        int avg=sum/k;
        return DFS(nums,k,flag,0,avg,0);
    }
    public boolean DFS(int[] nums,int k,boolean[] flag,int sum,int avg,int start){
        if (k==0){
            return true;
        }
        if (sum==avg){
            return DFS(nums, k-1, flag, 0, avg,0);
        }
        for (int i = start; i < nums.length; i++) {
            if (flag[i]||sum+nums[i]>avg){
                continue;
            }
            sum+=nums[i];
            flag[i]=true;
            if (DFS(nums, k, flag, sum, avg, i+1)){
                return true;
            }
            sum-=nums[i];
            flag[i]=false;

        }
        return false;
    }
    public boolean isAnagram(String s, String t) {

        if(s.equals(t)) return false;
        char[] ch1=s.toCharArray();
        char[] ch2=t.toCharArray();
        Arrays.sort(ch2);
        Arrays.sort(ch1);
        String s1=new String(ch1);
        String s2=new String(ch2);
        return s1.equals(s2);
    }
    public ListNode reverseList(ListNode head) {
        if (head==null||head.next==null){
            return head;
        }
        ListNode n1=null;
        ListNode n2=head;
        ListNode n3=head.next;
        while (n2!=null){
            n2.next=n1;
            n1=n2;
            n2=n3;
            if (n3!=null){
                n3=n3.next;
            }
        }
        return n1;
    }
    public int pivotIndex(int[] nums) {
        int sum=0;
        for (int n:nums) {
            sum+=n;
        }
        int cur=0;
        for (int i = 0; i < nums.length; i++) {
            sum-=nums[i];
            if (sum==cur){
                return i;
            }
            cur+=nums[i];
        }
        return -1;
    }
    public int[] twoSum(int[] numbers, int target) {
        Map<Integer,Integer> map=new HashMap<>();
        int[] arr=new int[2];
        int length=numbers.length;
        for (int i = 0; i < length; i++) {
            if (!map.containsKey(numbers[i])){
                map.put(numbers[i],i);
            }

        }
        for (int i = 0; i < length; i++) {
            if (map.containsKey(target-numbers[i])){
                arr[0]=i;
                arr[1]=map.get(target-numbers[i]);
            }
        }
        Arrays.sort(arr);
        return arr;
    }
    private int oneNum(int i) {
        int count=0;
        while (i!=0){
            count++;
            i=i&(i-1);
        }
        return count;
    }
    public int[] countBits(int n) {
        int[] arr=new int[n+1];
        arr[0]=0;
        for (int i = 1; i <= n; i++) {
            arr[i]=oneNum(i);
        }
        return arr;
    }



    public String addBinary(String a, String b) {
        String str="";
        int aIndex=a.length()-1;
        int bIndex=b.length()-1;
        int sum=0;
        while (aIndex>=0||bIndex>=0){
            char aChar=aIndex>=0?a.charAt(aIndex):'0';
            char bChar=bIndex>=0?b.charAt(bIndex):'0';
            sum+=aChar-'0'+bChar-'0';
            if (sum==0){
                str='0'+str;
            }else if (sum==1){
                str=sum+str;
                sum=0;
            }else if (sum==2){
                str='0'+str;
                sum=1;
            }else if (sum==3){
                str='1'+str;
                sum=1;
            }
            aIndex--;
            bIndex--;
        }
        if (sum!=0){
            str='1'+str;
        }
        return str;
    }
    public boolean isPalindrome(String s) {
        s=s.toLowerCase();
        if (s==null||s.length()==0){
            return true;
        }
        char[] chars=s.toCharArray();
        int left=0;
        int right=chars.length-1;
        while (left<right){
            while (left<right&&!Character.isDigit(chars[left])&&!Character.isAlphabetic(chars[left])){
                left++;
            }
            while (left<right&&!Character.isDigit(chars[right])&&!Character.isAlphabetic(chars[right])){
                right--;
            }
            if (chars[left]!=chars[right]){
                return false;
            }else {
                left++;
                right--;
            }
        }
        return true;
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (k==1||nums==null||nums.length==0){
            return nums;
        }
        Deque<Integer> deque=new LinkedList<>();
        List<Integer> list=new ArrayList<>();
        int max= Integer.MIN_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (deque.size()<k){
                deque.offer(nums[i]);
                max=Math.max(nums[i],max);
            }else {
                list.add(max);
                int min=deque.removeFirst();
                deque.offerLast(nums[i]);
                if (max==min){
                    max=Integer.MIN_VALUE;
                    for (int num:deque) {
                        max=Math.max(max,num);
                    }
                }else if (max<nums[i]){
                    max=nums[i];
                }
            }
        }
        if (max!=Integer.MIN_VALUE){
            list.add(max);
        }
        int[] arr=new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i]=list.get(i);
        }
        return arr;
    }
}
